\chapter{Algoritmo Propuesto}

\section{Diseño}
A continuación mostramos un pseudocódigo que resume el comportamiento
ge\-ne\-ral del algoritmo implementado:\\

\begin{algorithm}
\label{pseudo}
\begin{algorithmic}[1]

\STATE $iteracion \gets 1$
\STATE $poblacion \gets$ generar población inicial
\STATE evaluar el fitness de cada individuo de la $poblacion$
\WHILE {$ iteracion \leq MAXITERACIONES $}
	\STATE 	$padres \gets$ seleccionar aleatoriamente individuos
	\IF {$iteracion$ mod 150 = 0}
		\STATE $hijos \gets$ realizar busqueda local sobre $padres$
	 \ELSE
	 	\STATE $hijos \gets$ realizar operaciones geneticas sobre $padres$
	\ENDIF
	
	\STATE	evaluar el fitness de cada individuo en $hijos$
	\STATE	$poblacion \gets$ crear una nueva poblacion a partir de $poblacion$ e
 $hijos$
	\STATE $iteracion \gets iteracion + 1$
\ENDWHILE
\end{algorithmic}
\end{algorithm}

\subsection{Representación}
Basándonos en el dominio del rompecabezas decidimos modelar a los cromosomas
mediante una matriz que representa el tablero y a los genes
 mediante 4-tuplas que representan las piezas (ver figura
 \ref{fig:piezas}).
Cada una de las proyecciones de la 4-tupla contiene un número entero entre 0 y 22 
que representan una combinación color/forma posible de los bordes de las
piezas.\\

En la primer posición de la 4-tupla se encuentra la combinación perteneciente al
borde superior de la pieza, en la segunda posición la perteneciente al borde
derecho, en la tercer posición la del borde inferior y en la cuarta posición la
del borde izquierdo. El número 0 representa la combinación gris/plano reservada
para los bordes del tablero.\\

Debido a la facilidad de mapeo entre el problema real y su modelado, a lo largo
del trabajo nos referiremos de forma indistinta entre matriz y tablero y
entre pieza y tupla.\\

\begin{displaymath}
\mathbf{X} = 
\left( \begin{array}{cccc}
<0, 1, 1, 0>	&	<0, 1, 2, 1> 	&	 <0, 3, 4, 1>	&	<0, 0, 3, 3>	 \\
<1, 2, 3, 0>	&	<2, 2, 4, 2> 	&	 <4, 4, 5, 2>	&	<3, 0, 1, 4>	 \\
<3, 5, 3, 0>	&	<4, 4, 5, 5> 	&	 <5, 2, 5, 4>	&	<1, 0, 3, 2>	 \\
<3, 1, 0, 0>	& 	<5, 3, 0, 1>	&	 <5, 1, 0, 3>	&	<3, 0, 0, 1>	 
\end{array} \right)
\end{displaymath}
\\
\begin{figure}[ht!]
\centering
\includegraphics[width=0.35\textwidth]{imagenes/eternity2_4_4_2.jpg}
\caption{Ejemplo de representación de un tablero de 4 x 4}
\label{fig:piezas}
\end{figure}


\subsection{Población Inicial}
Los cromosomas de la población inicial son generados principalmente de forma
aleatoria, tanto en ubicación de las piezas como en la rotación de las mismas. 
Para los casos particulares de las piezas bordes y las esquineras, las mismas son
ubicadas aleatoriamente en bordes y esquinas respectivamente tomando en cuenta 
que el/los bordes grises de las piezas coincidan con el/los bordes grises del
tablero.
De esta forma se consiguen soluciones iniciales mejores a las elegidas totalmente al
azar.\\

Con el fin de evitar la construcción de soluciones rotadas del rompecabezas
decidimos fijar en esta etapa la pieza de la esquina superior izquierda del
tablero. Consecuencia de esto, todos los cromosomas contendrán en la
posición $X_{11}$ al mismo gen.\\



\subsection{Función de Evaluación}
La función de evaluación de una solución (individuo, cromosoma) consiste en
contar la cantidad de los bordes de las piezas adyacentes que coinciden
en forma y color. No tomaremos en cuenta los bordes ni esquinas, ya que es un
invariante para nosotros que los mismos se encuentren posicionados correctamente
durante todo el algoritmo.

Dada la matriz $X$ que representa el tablero y las tuplas
$x_{ij}$ que representan las piezas, definimos las siguientes funciones y operaciones:\\

\noindent Sea $t$ una 4-tupla:

\noindent 
$\Pi_l(t)$ devuelve la primer componente de la tupla (borde izquierdo).\\
$\Pi_t(t)$ devuelve la segunda componente de la tupla (borde superior).\\
$\Pi_r(t)$ devuelve la tercer componente de la tupla (borde derecho).\\
$\Pi_b(t)$ devuelve la cuarta componente de la tupla (borde inferior).\\

\noindent Sean $x$ e $y$ dos números enteros, definimos la siguiente función:
\begin{displaymath}
iguales(x, y) = 
\left\{ \begin{array}{ll}
1	&	\mbox{si } x = y \\
0	&	\mbox{si } x \neq y 
\end{array} \right.
\end{displaymath}\\

\noindent Definimos entonces la función de evaluación $Ft(X)$ de la siguiente
manera:
\begin{eqnarray}
Ft(X)	& = &	\sum_{\substack{1 \leq i \leq n \\ 1 \leq j < n}}
				\biggl( iguales(\Pi_r(x_{i, j}), \Pi_l(x_{i, j+1})) \biggr) +	 
				\sum_{\substack{1 \leq i < n \\ 1 \leq j \leq n}}
				\biggl( iguales(\Pi_b(x_{i, j}), \Pi_t(x_{i + 1, j})) \biggr) \nonumber
\end{eqnarray}

De esta forma, el mayor valor que puede tomar la función de evaluación en un
tablero cuadrado de $n \times n$ es de $2 \times n \times (n-1)$ y representa una
solución exacta.
Para nues\-tro caso, el tablero es de $16 \times 16$ por lo que el valor de una
solución exacta será de 480.
\\

\subsection{Selección}
Para seleccionar los individuos de una población que serán utilizados como
padres en la generación de la nueva población probamos dos técnicas comunmente
utilizadas. En una primera instancia utilizamos Roulette Wheel Selection
\cite{Zbigniew} que consiste en asociar una probabilidad de ser elegido a cada uno de los
individuos de la población basándose en la función de evaluación. Cuanto mayor
sea el valor de la función de evaluación, mas posibilidades tiene el individuo
de ser elegido.
De esta manera se intenta ampliar el espacio de búsqueda y disminuir la probabilidad de entrar 
en un máximo local y, a la vez, darle mayor importancia a aquellos individuos
que poseen una buena carga genética. En segundo lugar probamos 
seleccionando los individuos simplemente al azar.\\

Luego de realizar varias pruebas, decidimos dejar en la implementación final la
elección aleatoria de los individuos. Las pruebas realizadas con Roulette Wheel
Selection nos arrojaron resultados similares en cuestión de fitness, pero una
pequeña y obvia penalización en la performance del algoritmo, la que le quitó
importacia a su utilización.


\subsection{Operadores}
A continuación comentaremos los operadores utilizados en el algoritmo mediante
los cuales se realizan las operaciones que dan lugar a los nuevos individuos.
Cabe aclarar que siempre trabajamos con soluciones legales respecto al dominio del
rompecabezas, en el sentido de que los operadores no mezclan piezas entre
distintas soluciones ni ubican piezas bordes o esquineras en la zona interior
del tablero, más aún, siempre las piezas bordes y esquineras se ubican de forma
tal que sus bordes grises coincidan con los bordes del tablero.\\

\subsubsection{Mutación}
El algoritmo utiliza tres operadores distintos de mutación. La elección del
o\-pe\-ra\-dor utilizado se determina en tiempo de ejecución basado en una
probabilidad asignada a cada uno de los mismos.\\

\noindent \textbf{Intercambio de Filas}\\
Consiste en intercambiar todas las piezas entre dos filas del tablero. Las filas
a intercambiar son seleccionadas de manera aleatoria teniendo en cuenta no
utilizar las filas de los bordes del tablero. Durante el intercambio, las piezas
son ubicadas exactamente en la misma columna donde se encontraban
originalmente, es decir, solo cambian de fila.\\

\noindent \textbf{Intercambio de Columnas}\\
Idem al intercambio de filas pero entre columnas.\\

\noindent \textbf{Intercambio de Piezas}\\
El intercambio de piezas consiste en elegir dos piezas al azar e intercambiar
las mismas. Dentro de la selección se incluyen bordes y esquinas, pero con la
salvedad que las mismas se pueden intercambiar solo con otro borde o esquina
respectivamente. En estos últimos
casos, las piezas son rotadas hasta que coincidan con los bordes del tablero
para mantener la legalidad de la solución.\\
Siempre que
una pieza interior es intercambiada por otra, las mismas son rotadas hasta conseguir maximizar la
cantidad de piezas vecinas coincidentes en bordes de sus nuevas ubicaciones.
Esto último permite por un lado, conseguir mejores resultados en cuanto al
fitness, y por otro, lograr diversidad en las soluciones, ya que al rotar la
pieza para su mejor ubicación se genera una nueva rama de oportunidades.

\subsubsection{Crossover}
\noindent \textbf{Copia de región}\\
El operador consiste en copiar una región de piezas de un tablero en otro. Es un
crossover entre dos tableros que genera un solo offspring. Para llevar a cabo la
operación, se selecciona una región de manera aletoria del segundo tablero y se 
intercambian y rotan las fichas del primer tablero hasta lograr que
quede esa región con la misma configuración que el segundo.\\

La selección de la región a copiar dentro del tablero se realiza de forma
aleatoria y la dimensión de la región es proporcional al tamaño del
rompecabezas. Para el caso del EternityII, la dimensión de la región que nos
arrojó mejores resultados es de $8 \times 8$.

\subsection{Búsqueda Local}
Tal como puede observarse en el pseudocódigo de nuestro algoritmo (sección
~\ref{pseudo}), cada cierto número de iteraciones realizamos una búsqueda
local en algunos de los individuos de la población. La elección de los
individuos que participarán de la misma se realiza utilizando Roulette Wheel
Selection \cite{Zbigniew}.\\

La búsqueda local consiste, básicamente, en realizar de forma reiterada un
intercambio de piezas dentro del tablero, rotando además las mismas para que se
ajusten lo mejor posible a sus nuevas ubicaciones. Este procedimiento se realiza
para cada uno de los individuos seleccionados.
En cada iteración de la búsqueda local, se arma una matriz $W$ del
mismo tamaño del tablero $X$ que ponderará la elección de piezas a intercambiar.
El valor de cada $w_{ij}$ se calcula teniendo en cuenta la cantidad de
piezas adyacentes que no coinciden en bordes con la pieza $x_{ij}$ del tablero. 

\begin{eqnarray}
w_{ij}	& = &	(sumarAdyacentesNoCoincidentes(x_{ij}) + 1)^C \nonumber
\end{eqnarray}

La idea es que aquellas piezas que se encuentran peor ubicadas tengan mas
pro\-ba\-bi\-li\-dad de ser seleccionadas para el intercambio.\\

Una vez armada la matriz de pesos se selecciona de forma aleatoria una primer pieza. 
La elección, como mencionamos anteriormente, se realiza de forma tal que
aquellas piezas que tengan un peso mayor en la matriz $W$ tengan más
posibilidades de ser seleccionadas. Luego se procede a ajustar la matriz de pesos quitando (poniendo en 0) aquellos
valores $w_{ij}$ que no deben ser tomados en cuenta para seleccionar la segunda
pieza. Por ejemplo, si la primer pieza seleccionada pertenece a un borde,
entonces se ponen en 0 todas las piezas interiores y las esquineras, ya que de
no hacerlo se pone en riesgo la legalidad de nuestras soluciones.
Luego se procede con la selección de la segunda pieza de la misma forma que se
hizo con la primera y por último el intercambio de las mismas. Esta operación se
repite un número constante de veces.

\begin{displaymath}
\mathbf{W} = 
\left( \begin{array}{cccc}
(0 + 1)^C	&	(1 + 1)^C 	&	(0 + 1)^C	&	(0 + 1)^C	 \\
(1 + 1)^C	&	(3 + 1)^C 	&	(2 + 1)^C	&	(1 + 1)^C	 \\
(2 + 1)^C	&	(1 + 1)^C 	&	(1 + 1)^C	&	(0 + 1)^C	 \\
(1 + 1)^C	& 	(0 + 1)^C	&	(1 + 1)^C	&	(0 + 1)^C	 
\end{array} \right)
\end{displaymath}
\\

\begin{figure}[ht!]
\centering
\includegraphics[width=0.35\textwidth]{imagenes/eternity2_4_4_n.jpg}
\caption{Ejemplo de matriz de pesos para un tablero sin armar}
\label{overflow}
\end{figure}


\subsection{Reemplazo}
Una vez seleccionados los individuos y realizadas las operaciones sobre los
mismos, se prosigue con la formación de la nueva generación poblacional. Para esto es necesario 
reemplazar algunos individuos de la población anterior con los recientemente obtenidos. 
El reemplazo se realiza de forma elitista, es decir, se seleccionan de la población anterior 
los individuos que peores resultados tienen en cuanto a la función de evaluación
y se los reemplaza por los nuevos, permitiendo de ésta manera la convivencia de
padres e hijos dentro de la población.\\

\section{Implementación}
La implementación consiste principalmente de dos módulos bien definidos, el primero el algoritmo 
genético y el segundo una interfaz gráfica que permite visualizar las soluciones, ejecutar pruebas  
y modificar algunos parámetros. En ambos casos, el desarrollo se realizó utilizando el lenguaje de
 programación Java. \\
 
A continuación se muestra un diagrama con las principales clases que
intervienen en la solución:\\

\newpage
\begin{figure}[H]
\centering
\includegraphics[width=1\textwidth]{imagenes/ClassDiagram.pdf}
\caption{Diagrama con principales clases}
\end{figure}
\newpage

Para la visualización de las piezas de los rompecabezas se reemplazó cada
combinación color/patrón por un color único.\\

La implementación de la búsqueda local la realizamos utilizando varios hilos de ejecución para poder 
optimizar más de una solución a la vez y poder así disminuir el tiempo de
procesamiento. La cantidad de threads que utilizamos varía según la cantidad de
núcleos de la CPU utilizada.

\subsection{Parámetros}
La determinación de los parámetros fue realizada durante la etapa de diseño y
prueba del algoritmo. Los resultados que motivaron las decisiones tomadas 
pueden encontrarse en el apéndice \ref{app:resultados}. A continuación se enumeran los
principales parámetros utilizados:

\begin{itemize}
\item Tamaño de la poblacion: $15$ individuos.
\item Control de parada del algoritmo: por número de iteraciones.
\item Probabilidad de mutación: $15\%$.
	\begin{itemize}
	  \item Probabilidad de RowExchangeMutationOperator: $10\%$.
	  \item Probabilidad de ColumnExchangeMutationOperator: $10\%$.
	  \item Probabilidad de SwapAndRotateMutationOperator: $80\%$.
	\end{itemize}
\item Tamaño de bloque de RegionExchangeCrossoverOperator:
$\lfloor\frac{n}{2}\rfloor \times \lfloor\frac{n}{2}\rfloor$
\item Ejecución de búsqueda local: cada 150 iteraciones
\item Individuos a realizar búsqueda local por ejecución: $50\%$ de la
población.
\item Iteraciones por cada búsqueda local: 2000.
\item Threads por ejecución de búsqueda local: cantidad de núcleos del CPU.
\item Elitismo: $20\%$ de la población.
\end{itemize}

